The pertinent prior art concerns pipelining computations on one hand and arithmetic string codes on the other. In this regard, reference should be made to T. C. Chen, "Overlap and Pipeline Processing," pages 375-431, Introduction to Computer Architecture, 1975, published by SRA; Kai Hwang, "Computer Arithmetic," pages 379-382; Langdon et al, U.S. Pat. No. 4,122,440; issued Oct. 24, 1978; and the two Langdon and Rissanen co-pending U.S. patent applications U.S. Ser No. 048,318, filed June 14, 1979, and U.S. Ser No. 098,285, filed Nov. 29, 1979.
Chen and Hwang references characterize pipelining as an extreme form of multiple overlap operation upon a data stream in which the completion signals are replaced by synchronizing time clock pulses. Pipelining is further characterized as a processing technique aiming for a steady throughput. As noted by Chen, processing power is decentralized. It is, however, distributed more or less uniformly over the processing path by coupling processing elements into a chain. One can observe precedence dependence and still achieve a total work rate equal to the sum of the work rate of each of the processing elements. In this type of environment, throughput suffers when the computational results are interdependent, rather than independent, among the stages in the chain. Significantly, the decoding of an arithmetic string code is an illustration of such interdependence when contemplating a pipeline burp-free process.
In binary arithmetic encoding, one of two possible symbols (0 or 1) are encoded at each step. Generality derives from the fact that blocked (and other) data can be encoded in steps, one for each bit. The arithmetic encoding process as described in the above-named Langdon, et al, references does not use any predetermined code word. More particularly, as described in the copending 285 application, the encoding process directly uses an estimate of the probability of occurrence of a "0" or "1". This use of a probability estimate is the property which distinguishes arithmetic code strings from the compression encoding approach of Huffman. Huffman codes are described in Abramson, "Information Theory and Coding," McGraw Hill, 1963, pages 77-85.
In the Langdon, et al, application, it is the estimate of the probability of the less probable symbol (LPS) which is approximated to the nearest value of the form 2.sup.-k. Furthermore, an ordered pair (L, k)=Q is used as a control descriptor in which "L" denotes the LPS value and "k" denotes the integer power of 2. The descriptor Q saves storage space over code words which otherwise could become large and also is convenient for adaptation.
The binary arithmetic coding as described in the co-pending 285 application generates an instantaneous FIFO binary arithmetic code string C(sb). This string is recursively formed by the high to low order pairwise combining of digits of a decodable set of relatively shifted finite binary number strings C(s) and/or A(sb). C(s) is the encoded string corresponding to source string s, and A(sb) is an augend function for symbol b given prior string s. The encoding action is in response to each binary symbol b occurring in the symbol string s. In this latter regard "q" of the lowest order bits of each string C(s) and A(sb) are combined during each recursion. Lastly, arithmetic code string carries are controlled through control character insertions after predetermined length runs of consecutive 1's.
In order to appreciate the subsequent discussion of the invention, consideration should first be given to aspects of the prior art FIFO encoding and decoding. Firstly, the encoder is similar to a finite state machine whose internal state may be represented by number T. Also, as a processor of values in recursive relations the encoder contains a q bit "working end" of the code string in a designated register. The problem is for the encoder to ascertain whether the symbol b to be encoded is the less probable symbol (LPS) or the more probable symbol (MPS), as well as determining the integer value control parameter (skew number) k. In the encoding action, the encoder forms a trial augend (TA). TA is related to T and k by TA=T.times.(1-2.sup.-k).
If the encoder determines that the symbol to be encoded is LPS, then the encoder adds TA to the working end of the code stream so as to form a new working end. At the same time, the encoder left shifts out k bits from the working end of the code string and similarly shifts the contents of the designated register (register C). The internal state T of the encoder remains unchanged. On the other hand, if the symbol to be encoded is MPS, the encoder does not add TA to the working end of a code string. Rather, the encoder tests for normalization. The test for normalization involves the leftmost bit of TA. If the leftmost bit is "1", then TA is already "normalized". A normalized value of T is assigned the value TA. If the leftmost bit of TA is "0", then the most significant bit in designated register C is outputted. Next, TA is normalized: left shifted one bit and assigned as the value of T. The designated register C is left shifted one bit.
It is apparent that the basic operations for encoding are adding, subtracting, and shifting.
Relatedly, the decoder as described in the copending 285 application needs only to subtract and shift. The decoder has the q most significant bits of the code stream in a designated register C and has an internal state represented by the number T.
Assuming that the decoder has knowledge of the integer-valued control parameter k, then the decoder forms trial augend TA according to TA=T.times.(1-2.sup.-k). At this point, the value TA is substracted from the contents of register C. If the difference is negative, a borrow-out occurs and it is concluded that the decoded symbol was the MPS. If a normalization occurs, TA is shifted left to form T. The contents of register C are left shifted as well.
If the difference TC=C-TA is positive, then the decoded symbol is LPS. On this occasion, the difference TC=C-TA is shifted left by k bit positions. The difference is also restored to register C with the "fill" coming from the next k most significant bits of the code stream C(s). Again, the value of the internal state T remains unchanged.